package io.github.hadyang.leetcode.offer;

import org.junit.Test;

/** @author haoyang.shi */
public class NumberOf1Between1AndN {

  @Test
  public void test() {
    //        System.out.println(NumberOf1Between1AndN_Solution(0));
    //        System.out.println(NumberOf1Between1AndN_Solution(10));
    //        System.out.println(NumberOf1Between1AndN_Solution(13));
    //        System.out.println(NumberOf1Between1AndN_Solution(55));
    System.out.println(NumberOf1Between1AndN_Solution(21345));
  }

  public int NumberOf1Between1AndN_Solution(int n) {
    int[] res = {0};
    NumberOf1Between1AndN(res, n);

    return res[0];
  }

  private void NumberOf1Between1AndN(int[] res, int n) {
    // 假设 num=21345
    String num = String.valueOf(n);
    int firstNum = num.charAt(0) - '0';

    if (num.length() == 1) {
      if (firstNum > 0) res[0]++;
      return;
    }

    String nextNum = num.substring(1);
    int nextN = Integer.valueOf(nextNum);

    // 数字 10000 ～ 19999 的第一位中的个数
    if (firstNum > 1) {
      res[0] += Math.pow(10, num.length() - 1);
    } else if (firstNum == 1) {
      res[0] += nextN + 1;
    }

    // 1346 ～ 21345 除第一位之外的数的个数
    res[0] += firstNum * (num.length() - 1) * Math.pow(10, num.length() - 2);

    NumberOf1Between1AndN(res, nextN);
  }
}
